#Problem 1a

x = int(input("Enter a an integer:"))
if x==1:
    print("EECE 230 is fun")
elif x ==2: 
    print("EECE 230 is easy")
elif x==3: 
    print("EECE 230 is fun and easy.")
else: 
    print("Invalid input")

    
#Problem 1b

while True: 
    x = input("Is EECE 230 fun and easy? ")
    if x =="YES" or x =="yes" or x =="Yes": 
        print("Thank you for your input")
        break

#Problem 1c

def funAndEasy(s):
    i = s.find("EECE 230")
    if i==-1: 
        return s
    else: 
        return s[:i+8]+" (which is fun and easy)"+s[i+8:]


print(funAndEasy("I am taking EECE 230 this semester"))
print(funAndEasy("... EECE 230 ... EECE 230 ..."))
print(funAndEasy("60 points so far"))


#-------------------------------------------------------------------------------------
#-------------------------------------------------------------------------------------


#Problem 2a

m = int(input("Enter value of m:"))


#############################################
if m>=1:
    L = [i for i in range(1,m)]+[m]+[i for i in range(m-1,0,-1)]
else: 
    L = []
print("Pyramid-shaped list:",L)

##############################################
## Solution 2: 
#print("Solution 2:")
#if m>=1: 
#    L = list(range(1,m))+[m]+list(range(m-1,0,-1))
#else: 
#    L = []
#print("Pyramid-shaped list:",L)
#
##############################################
## Solution 3: 
#L = []
#if m>=1: 
#    for i in range(1,m):
#        L.append(i)
#    L.append(m)
#    for i in range(m-1,0,-1):
#        L.append(i)
#print("Solution 3:")
#print("Pyramid-shaped list:",L)
#
##############################################
## Solution 4: 
#if m >=1:
#    L = (2*(m-1)+1)*[0]
#    for i in range(1,m):
#        L[i-1]=i
#    L[m-1]=m
#    for i in range(1,m):
#        L[m-1+i]=m-i
#else: 
#    L=[]
#print("Solution 4:")
#print("Pyramid-shaped list:",L)
#
#############################################
## Solution 5:
#
#L=[m-abs(m-i) for i in range(1,2*m)]
#
#print("Pyramid-shaped list:",L)
#############################################


#Problem 2b

def buildString(m):
    s = "*"
    for i in range(1,m+1):
        s=s+"1"*i+"*"
    return s

print(buildString(-1))   
print(buildString(0))
print(buildString(1))
print(buildString(2))
print(buildString(3))
print(buildString(4))
print(buildString(5))
print(buildString(6))


#-------------------------------------------------------------------------------------
#-------------------------------------------------------------------------------------


#Problem 3VerySlow

## Given an integer n, does there exist integers x and y 
## such that x^2+y^2 = n? If so find such a pair 

# O(n^2) solution 

n = int(input("Enter an integer: "))
sumOfSquares = False
for x in range(n+1):
    for y in range(n+1): 
        if x*x+y*y==n: 
            sumOfSquares = True
            break
    if sumOfSquares: 
        break

if sumOfSquares: 
    print("YES:",n,"=",str(x)+"^2 + "+str(y)+"^2") 
else: 
    print("NO") 




    
#Problem 3Slow

## Given an integer n, does there exist integers x and y 
## such that x^2+y^2 = n? If so find such a pair 

# O(n) solution 

n = int(input("Enter an integer: "))
x=0
sumOfSquares = False
while x*x <=n:
    diff=n-x*x
    y=0
    while y*y <=diff:
        if y*y == diff:
            sumOfSquares = True
            break
        y+=1
    if sumOfSquares: 
        break
    x+=1
    
if sumOfSquares: 
    print("YES:",n,"=",str(x)+"^2 + "+str(y)+"^2") 
else: 
    print("NO") 

#Problem 3Fast





## Given an integer n, does there exist integers x and y 
## such that x^2+y^2 = n? If so find such a pair 

# O(sqrt(n)*log(n)) solution  

n = int(input("Enter an integer: "))

sumOfSquares = False 
x=0    
while x*x <=n:
        diff = n-x*x
        # search for y s.t. y*y = diff using bisection method as in PA2
        low=0
        high=diff
        mid = (low+high)//2
        while low <= mid:
        # Since low is updated below to mid+1 and high to mid-1,  
        # the search interval size decrease by at least one after each iteration. 
        # Thus if n is not a square, then low will be eventually larger than mid
            if mid*mid == diff:
                sumOfSquares = True 
                break 
            elif mid*mid > diff:
                high=mid-1
            else:
                low=mid+1
            mid = (low+high)//2
        if sumOfSquares: 
            break
        x+=1
    
if sumOfSquares: 
    print("YES:",n,"=",str(x)+"^2 + "+str(mid)+"^2") 
else: 
    print("NO") 





    
#Problem 3VeryFast


## Given an integer n, does there exist integers x and y 
## such that x^2+y^2 = n? If so find such a pair 
n = int(input("Enter an integer: "))


                
## Bonus 

# Idea: 
# If x and y  exist, then we must have 0<=x<=s and 0<=y<=s, 
# where s = floor(sqrt(n))
# We can find s in O(log(n)) steps using bisection as in PA2 
#  or in O(sqrt(n)) steps using the naive method 
# Given s, the key idea is to search for the pair (x,y) in 
#  the  range 0<=x<=s and 0<=y<=s
# Intialize x to 0 and y to s
# Compare x^2+y^2 to n
# If <,we know that we can eliminate x = 0. Thus, we increment x
# If =, we are done 
# If <, we know that we can eliminate y = s. Thus, we decrement y
# We repeat this process until either (x,y) is found or we hit x =-1 
#  or y=-1, in which case we know that no such (x,y) exists 
# In the worst case, this process takes 2(s+1)+1 steps, thus the total 
#  time is O(s)=O(sqrt(n)) arithemtic operations
# Another observation which speeds up the algorithm by a factor of 2
#  is that we can assume without loss of generality that x<=y. Thus, 
#  instead of searching in the rectangle sepcified by (0,0), (0,s), 
#  (s,0), and (s,s), we focus on the triangle formed  by the points 
#  (0,0),(0,s), and (s,s). 
# With this in mind, we repeat the above process until either (x,y) 
#  is found or we hit x =-1, y=-1, or x>y

    
## First, find s 
s = 0
while s*s<=n: 
    s+=1
if s*s>n: 
    s-=1
## Searching inside the triangle formed by (0,0), (0,s) and (s,s)
x = 0
y = s 
sumOfSquares = False
while x>=0 and y>=0 and x<=y: 
    if x*x+y*y<n:
        x+=1  
    elif x*x+y*y==n:
        sumOfSquares = True 
        break
    else: #  x*x+x*y > n:
        y-=1

if sumOfSquares: 
    print("YES:",n,"=",str(x)+"^2 + "+str(y)+"^2") 
else: 
    print("NO") 


#-------------------------------------------------------------------------------------
#-------------------------------------------------------------------------------------


#Problem 4


########
# a)
def minDistance(L):
    n = len(L)
    minDist = n
    for i in range(n):
        for j in range(i+1,n):
            if L[i]==L[j] and minDist> j-i:
                minDist=j-i
    return minDist 

print("a)")
print(minDistance([17,10,43,14,-3,2,17]))
print(minDistance([17,10,43,14,-3,2,10]))
print(minDistance([17,10,43,14,-3,2,17,14,5,-3,3,12,17]))
print(minDistance([17,10,10,14,-3,14,17]))
print(minDistance([10,10,10]))
print(minDistance([10]))
print(minDistance([]))

#########
# b)
print("\nb)")       

def maxMinDistanceSlow(L): # Worst case O(n^3)
    """ Find maximal min distance between repeated elements 
        in sublist of L of size n//2 """
    n = len(L)
    m = n//2
    maxMinDist =  minDistance(L[0:m])
    iBest = 0
    for i in range(1,n-m+1): # need i+m-1<n, i.e., i<n-m+1
        minDist = minDistance(L[i:i+m])
        if minDist>maxMinDist: 
           maxMinDist=minDist
           iBest = i
    return  (maxMinDist, L[iBest:iBest+m])
print("Slow solution:")
print(maxMinDistanceSlow([10,10,14,10,11,14,17,14,3,-3,3]))

def maxMinDistanceFast(L): # O(n^2)
    """ Find maximal min distance between repeated elements 
        in sublist of L of size n//2 """

    n = len(L)
    m = n//2
    #Idea: 
    #  1.Construct the index list ind[0...n-1], where   
    #   ind[j]= index of closest elements to the right of L[j], which is equal  
    #     to L[j] and within distance m-1 from j, i.e., 
    #   ind[j]=min k, for j< k< min(j+m,n) such that L[j]=L[k]
    #   If all elements to the right of L[j] are distinct from L[j], set ind[j]=n
    #  2.Now, efficiently find the maxMinDist with the help of list ind using  two nested loops: 
    #      For i = 0,..., m-n: 
    #          Find min distance of L[i:i+m] using a single loop on the 
    #          list ind[i:i+m] by finding: 
    #          min of ind[j]-j for  i<=j<i+m  s.t. ind[j]<i+m 


    def buildIndexList(L,m):
        n = len(L)
        ind = [n]*n
        for j in range(n):
            for k in range(j+1,min([j+m, n])):
                if L[j]==L[k]:
                    ind[j]=k
                    break
        return ind
                
    def fastMinDistance(L,m,i,ind): 
        """ Efficiently find minDistance(L[i:i+m]) with the help of  list ind """ 
        minDist = m
        for j in range(i,i+m): 
            if ind[j]<i+m and ind[j]-j< minDist: 
                minDist = ind[j]-j     
        return minDist 

    # Buid list ind 
    ind = buildIndexList(L,m)
    # Now, efficiently find maxMinDist with the help of  ind: 
    iBest = 0
    maxMinDist = 0
    for i in range(n-m+1):
        minDist = fastMinDistance(L,m,i,ind)
        if minDist>maxMinDist: 
           maxMinDist=minDist
           iBest = i
    return  (maxMinDist, L[iBest:iBest+m])

print("Fast solution:")
print(maxMinDistanceFast([10,10,14,10,11,14,17,14,3,-3,3]))